As will be understood by those skilled in the art, a syndrome comprises a basic element of a decoding procedure. In one example, the syndrome can be used to identify the bits in error.
One example of a decoder comprises a Bose, Chaudhuri, and Hocquenghem (“BCH”) decoder. A BCH decoder operates with BCH codes. BCH codes constitute a broad class of error-correcting and error-detecting codes. BCH codes are typically designed using the theory developed for Galois field (“GF”) arithmetic. Examples of BCH codes include binary BCH codes and Reed-Solomon codes. Hamming codes, for example, comprise a subset of binary BCH codes. BCH codes comprise a subset of cyclic codes, as will be understood by those skilled in the art.
A binary BCH code, in one example, is characterized by a block length N, an information vector length K, a number of bits per symbol m where N=2m−1, a primitive element α used to construct a Galois field GF(2m), a generator polynomial g(x), and a guaranteed error correction capability t. Commonly, those skilled in the art interchangeably employ the terms “vector” and “polynomial.” For example, the K-bit information vector u[0], . . . , u[K−1] is represented as the polynomial u(x)=u[K−1]xK−1+u[K−2]xK−2 +. . . +u[1]x+u[0], where the coefficients u[0], . . . , and u[K−1] are elements of GF(2m), and are binary in the case of binary BCH codes.
A detailed example is now presented for explanatory purposes. A K-bit information vector u(x) is encoded into an N-bit codeword v(x) by polynomial multiplication with g(x). In one example, the encoder is initialized to some value, such as zero, before the polynomial multiplication. This codeword is transmitted, possibly corrupted by the channel, and received as a vector r(x). A BCH decoder estimates a decoded information vector w(x) based on r(x) and possibly additional information.
Several decoder techniques have been developed to estimate w(x) from r(x). In one example of a BCH decoder, syndromes are computed by evaluating the received vector r(x) at consecutive roots of the generator polynomial g(x). The syndromes characterize the difference from the received vector to the nearest codeword. So, the syndromes can be used in a decoder to correct this difference.
The properties of a generator polynomial, in one example, can suggest a design of a BCH decoder. One can assume, for example, that the necessary roots of the generator polynomial comprise at least 2t consecutive values αL+1, αL+2, . . . , αL+2t, where α represents the primitive element used to construct the Galois field GF(2m), and L represents a starting power of the roots. In one example, when the roots comprise α1, α2, . . . , α2t (L=0), it is understood by those skilled in the art that the syndromes sj for binary BCH codes possess a property as described by the following exemplary Equation (1).s2j=(sj)2j=1, . . . ,t  (1)Because of Equation (1), in one example, the odd-numbered syndromes can be first computed by evaluating the received vector r(x) at the necessary odd-powered roots of the generator polynomial. The even-numbered syndromes can then computed by using Equation (1). In this example, the number of operations in a BCH decoder can be reduced.
In another example, when the necessary roots of the generator polynomial are consecutive, the first root and error-correcting capability t comprise sufficient information to determine the subsequent roots of the generator polynomial. In this example, a BCH decoder can reduce the amount of information (e.g., memory usage) needed.
Computing syndromes typically comprises a computationally-intensive task because the computation typically involves polynomial evaluation using Galois field arithmetic. To compute syndrome sj directly, the received vector r(x) is evaluated at root αj+L, as follows in exemplary Equation (2).sj=r(αj+L)=rN−1(αj+L)N−1+rN−2(αj+L)N−2 +. . . +r1(αj+L)+r0  (2)Evaluating Equation (2), in one example, requires N−1 GF(2m) additions, N−1 general GF(2m) multiplications, and N−1 general GF(2m) exponentiations per syndrome.
When representing the Galois field elements as an m-tuple over a standard canonical basis (αm−1, . . . ,α, 1), GF(2m) addition is equivalent to a simple exclusive-OR operation. Further, GF(2) multiplication is equivalent to a logical AND operation for m=1. However, the general GF(2m) multiplications and general GF(2m) exponentiations typically have no simple implementation for m>1 in the standard canonical basis. To minimize the number of these exponentiations, one technique for evaluation of polynomials employs an iterative algorithm, such as Horner's rule. For instance, Equation (2) can be expressed as follows in exemplary Equation (3).sj=r(αj+L)=r(β)=( . . . ((rN−1β+rN−2)β+rN−3)β+ . . . +r1)β+r0 where β=αj+L  (3)On the one hand, Equation (3) eliminates the general GF(2m) exponentiations. On the other hand, Equation (3) nevertheless as a shortcoming requires N−1 general GF(2m) multiplications per syndrome.
To address the shortcoming of requiring GF(2m) multiplications in syndrome calculation, a number of hardware and software approaches have been offered. For example, certain hardware designs implement a general GF(2m) multiplier. One shortcoming of a typical hardware implementation of a general GF(2m) multiplier is the relatively large amount of power consumption required by the general GF(2m) multiplier.
Further, a number of software implementation that use lookup tables have been offered to perform general GF(2m) multiplication for syndrome calculations. In one example, the multiplicands are transformed from the standard canonical basis into an exponential representation by using lookup tables. In the exponential representation, integer arithmetic (i.e., addition, modulo) replaces GF(2m) multiplication. Once the integer result has been computed, a lookup table is used to transform the integer result into the standard canonical basis. For instance, if a and b are elements of GF(2m), the steps of a general GF(2m) multiplier in one software implementation for computing c=a×b are as follows.                if ((a==0)or(b==0))                    c=0                        else                    a′=LUT(a)            b′=LUT(b)            c′=(a′+b′)mod(2m−1)            c=LUT−1(c′)                        
In the above steps, LUT is the lookup table used to transform a number from the standard canonical basis into an exponential representation, and LUT−1 is the lookup table that transforms an exponential representation into the standard canonical basis.
This exemplary software implementation suffers from the use of lookup tables. As one shortcoming, the memory requirement of the lookup tables is proportional to 2m. For modest m, such as m=9, the memory requirement therefore undesirably exceeds 512 words. As another shortcoming, the required accessing of the lookup tables limits the processing capabilities of the software implementation. This use of the lookup table undesirably lowers the data rate that is sustainable for a software implementation.
Thus, a need exists for enhanced generation of a syndrome that is usable in a decoder.